package style.zcyLeetCode.a_0005_二叉树;

import java.util.LinkedList;

/**
 * 判断是否二叉搜索树  二叉搜索树：左小右大
 * 递归处理：中序遍历把节点值存放在list中，然后判断比对大小
 */
public class IsBST {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static boolean isBST(Node head) {
        if (head == null) {
            return true;
        }
        LinkedList<Node> inOrderList = new LinkedList<>();
        // 中序遍历
        process(head, inOrderList);
        int pre = Integer.MIN_VALUE;
        for (Node cur : inOrderList) {
            if (pre >= cur.value) {
                return false;
            }
            pre = cur.value;
        }
        return true;
    }

    public static void process(Node head, LinkedList<Node> inOrderList) {
        if (head == null){
            return;
        }
        process(head.left, inOrderList);
        inOrderList.add(head);
        process(head.right, inOrderList);
    }

    public static void main(String[] args) {

    }
}
